package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-12 
 * @Version: 1.0
 */

// todo 需要注意范围，时刻牢记左闭右开
public class LC105从前序与中序遍历序列构造二叉树 {

    Map<Integer,Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return findNode(preorder,0,preorder.length,inorder,0,inorder.length);

    }

    public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){

        if (preBegin>=preEnd || inBegin>=inEnd){
            return null;
        }

        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);

        int lenOfLeft = rootIndex - inBegin;

        root.left = findNode(preorder,preBegin+1,preBegin+1+lenOfLeft,inorder,inBegin,rootIndex);
        root.right = findNode(preorder,preBegin+1+lenOfLeft,preEnd,inorder,rootIndex+1,inEnd);

        return root;
    }
}
